class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0, n = nums.size();
        for (auto x : nums) sum += x;
        if (sum % 2 == 1) return false;

        vector<bool> arr(sum / 2 + 1);
        arr[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = sum / 2; j >= nums[i]; --j)
                if (!arr[j])
                    arr[j] = arr[j - nums[i]];
        }
        return arr[sum / 2];
    }
};